<!DOCTYPE html>  
<html>
    <meta charset="utf-8" />  
    <title>归并排序</title>  
<body>
    <h1>归并排序</h1>
    <h2>
        归并排序是第一个可以被实际使用的排序算法。
        你在本书中学到的前三个排序算法性能不好，
        但归并排序性能不错，其复杂度为O(nlogn)
    </h2>
    <p>
        归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，
        直到每个小数组只有一个位置，接着将小数组归并成较大的数组，
        直到最后只有一个排序完毕的大数组。
    </p>
</body>
<script> 
    // mergeSortRec的作用的将数组 分成若干哥长度为1的数组，merge负责排序并合并这些小数组
    const arr = [1,3,7,2,6,8,4,12,5]
    // const mergeSortRec = function(array){
    //     var length = array.length;
    //     if(length == 1){
    //         return array;
    //     }
    //     var mid = Math.floor(length/2),
    //         left = array.slice(0,mid),
    //         right = array.slice(mid,length);
    //     return merge(mergeSortRec(left),mergeSortRec(right))
    // }

    // var merge = function(left,right){
    //     console.log('left',left)
    //     console.log('right',right)
    //     var result = [],
    //         il = 0,
    //         ir = 0;
    //     while(il<left.length&&ir<right.length){
    //         if(left[il]<right[ir]){
    //             result.push(left[il++])
    //         }else{
    //             result.push(right[ir++])
    //         }
    //     }
    //     while(il<left.length){
    //         result.push(left[il++])
    //     }
    //     while(ir<right.length){
    //         result.push(right[ir++])
    //     }
    //     console.log('result',result)
    //     return result;
    // }
    // console.log(mergeSortRec(arr))
    
    const mergeSortRec = (arr)=>{
        let len = arr.length;
        if(len==1){return arr;};
        let piov = Math.floor(len/2);
        let arrF = arr.slice(0,piov);
        let arrR = arr.slice(piov,len);
        return merge(mergeSortRec(arrF),mergeSortRec(arrR))
    }

    function  merge(left,right){
        console.log(left,right)
        let il = 0;
        let ir = 0;
        let result = [];
        while(il<left.length&&ir<right.length){
            if(left[il]<right[ir]){
                result.push(left[il++]);
            }else{
                result.push(right[ir++]);
            }
        }
        while(il<left.length){
            result.push(left[il++]);
        }

        while(ir<right.length){
            result.push(right[ir++]);
        }
        return result
    }
    console.log(mergeSortRec(arr))
    

</script>  
</html>